package org.lyc.dp;

import java.util.Scanner;

/**
 * https://www.bilibili.com/video/BV1aa411f7uT?p=2&vd_source=65f5ad03ccd998407c9d802ca94f29fd
 * 一个青蛙一次可以跳上一级台阶, 也可以跳两级, 求青蛙跳上一个n(0~100)级台阶总共有多少种跳法.
 * 例如:
 * n=2 输出2
 * n=7 输出21
 * n=0 输出1
 *
 * @author Liu Yicong
 * @date 2024/1/31
 */
public class AFrogStep {
	static int n = 100;
	static int mod = 1000000008;

	public static void main(String[] args) {
		int[] dp = new int[101];//dp[i] 表示跳上第i级有多少种跳法
		dp[0] = dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2]) % mod;// 跳上第i级跳法包括两种情况, 从第i-1级跳1级,和从第i-2级跳两级.
		}
		System.out.println(dp[n]);
	}

}
